package main

import "fmt"

func main() {
	p := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
		},
	}
	q := &TreeNode{
		Val: 1,
		Right: &TreeNode{
			Val: 2,
		},
	}
	fmt.Println(isSameTree(p, q))
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}

	if q == nil {
		return false
	}

	if p == nil {
		return false
	}

	pq := []*TreeNode{p}
	qq := []*TreeNode{q}
	for len(pq) > 0 {
		levelSize := len(pq)
		if len(qq) != levelSize {
			return false
		}

		for i := 0; i < levelSize; i++ {
			pn := pq[0]
			pq = pq[1:]

			qn := qq[0]
			qq = qq[1:]

			if pn.Val != qn.Val {
				return false
			}

			if pn.Right != nil {
				pq = append(pq, pn.Right)

				if qn.Right == nil {
					return false
				} else if qn.Right.Val != pn.Right.Val {
					return false
				}
			}

			if pn.Left != nil {
				pq = append(pq, pn.Left)

				if qn.Left == nil {
					return false
				} else if qn.Left.Val != pn.Left.Val {
					return false
				}
			}

			if qn.Right != nil {
				qq = append(qq, qn.Right)
				if pn.Right == nil {
					return false
				} else if qn.Right.Val != pn.Right.Val {
					return false
				}
			}

			if qn.Left != nil {
				qq = append(qq, qn.Left)

				if pn.Left == nil {
					return false
				} else if qn.Left.Val != pn.Left.Val {
					return false
				}
			}

		}
	}

	return true
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
